package com.leetcode;

/*
    *********************************************
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
           佛祖保佑       永无BUG
 */

/**
 * 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头
 * @author wry
 * @description:
 * @date 9/4/25 PM7:58
 */
public class No147 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res = head;
        ListNode temp = head;
        while (temp != null) {
            ListNode next = temp.next;
            ListNode resTemp = res;
            if (temp.val <= resTemp.val) {
                temp.next = resTemp;
                res = temp;
            } else {
                while (resTemp.next != null && resTemp.next.val < temp.val) {
                    resTemp = resTemp.next;
                }
                temp.next = resTemp.next;
                resTemp.next = temp;
            }

            temp = next;
        }
        return res;
    }
}
